home *** CD-ROM | disk | FTP | other *** search
/ Aminet 21 / Aminet 21 (1997)(GTI - Schatztruhe)[!][Oct 1997].iso / Aminet / dev / c / BinaryTrees.lzh / ubi_sample.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-07-26  |  9.0 KB  |  220 lines
  1. /* ========================================================================== **
  2.  *                                ubi_sample.c
  3.  * ========================================================================== **
  4.  * Written by Chris Hertel.
  5.  * ========================================================================== **
  6.  *
  7.  *  $Log: ubi_sample.c,v $
  8.  *  Revision 0.2  1997/07/26 05:03:37  crh
  9.  *  Added code to print the module information.
  10.  *
  11.  *  Revision 0.1  1997/06/03 04:38:45  crh
  12.  *  Initial Revision.
  13.  *
  14.  *
  15.  * ========================================================================== **
  16.  */
  17. #include <stdio.h>              /* Standard I/O.     */
  18. #include <string.h>             /* String functions. */
  19. #include <stdlib.h>             /* Standard C library header. */
  20. #include <errno.h>              /* Error handling.   */
  21.  
  22. /* Note: Only one of the headers below should be included.  Comment out all
  23.  *       but one.  This determines which type of tree balancing you are using.
  24.  */
  25.  
  26. /*#include "ubi_BinTree.h"        /* Binary tree module. */
  27. #include "ubi_AVLtree.h"        /* AVL tree module.    */
  28. /*#include "ubi_SplayTree.h"      /* Splay tree module.  */
  29.  
  30. /* -------------------------------------------------------------------------- **
  31.  * Constants...
  32.  *
  33.  * Just some numbers we need.
  34.  */
  35.  
  36. #define NAMESIZE 240
  37.  
  38. /* -------------------------------------------------------------------------- **
  39.  * Typedefs...
  40.  *
  41.  *  Note: ulong is an unsigned long, oolong is a tea.
  42.  *
  43.  *  SampleRec    - This is the sample data record with which we will be
  44.  *                 playing.  It starts with a ubi_trNode structure (so that
  45.  *                 the tree functions can fiddle with it), the rest is data.
  46.  *                 In this case, we're just using a fixed-length character
  47.  *                 array.  In a "real" program, you could have all sorts
  48.  *                 of stuff.
  49.  *  SampleRecPtr - A pointer to a SampleRec.
  50.  */
  51.  
  52. typedef unsigned long ulong;
  53.  
  54. typedef struct {
  55.   ubi_trNode Node;
  56.   char       Name[NAMESIZE];
  57.   } SampleRec;
  58.  
  59. typedef SampleRec *SampleRecPtr;
  60.  
  61. /* -------------------------------------------------------------------------- **
  62.  * Global Variables...
  63.  *
  64.  *  We'll declare our tree header globally.  The structure is called a
  65.  *  ubi_trRoot, but it's really a housekeeping header with a pointer to the
  66.  *  tree's root node.
  67.  *
  68.  *  Root    - The tree header.
  69.  *  RootPtr - A pointer to the tree header.
  70.  */
  71.  
  72. static ubi_trRoot    Root;
  73. static ubi_trRootPtr RootPtr = &Root;
  74.  
  75. /* -------------------------------------------------------------------------- **
  76.  * Functions...
  77.  */
  78.  
  79. static int CompareFunc( ubi_trItemPtr ItemPtr, ubi_trNodePtr NodePtr )
  80.   /* ------------------------------------------------------------------------ **
  81.    * If we are going to sort the data, we will need to be able to compare the
  82.    * data.  That's what this function does.  A pointer to this function will
  83.    * be stored in the tree header.
  84.    *
  85.    *  Input:  ItemPtr - A pointer to the comparison data record.
  86.    *                    Take a look at the Insert(), Find() and Locate()
  87.    *                    functions.  They all take a parameter of type
  88.    *                    ubi_trItemPtr.  This is a pointer to the data to be
  89.    *                    compared.  In Find() and Locate(), it's a value that
  90.    *                    you want to find within the tree.  In Insert() it's
  91.    *                    a pointer to the part of the new node that contains
  92.    *                    the data to be compared.
  93.    *          NodePtr - This is a pointer to a node in the tree.
  94.    *  Output: An integer in one of three ranges:
  95.    *          < 0 indicates ItemPtr < (the data contained in) NodePtr
  96.    *          = 0 indicates ItemPtr = (the data contained in) NodePtr
  97.    *          > 0 indicates ItemPtr > (the data contained in) NodePtr
  98.    * ------------------------------------------------------------------------ **
  99.    */
  100.   {
  101.   char *A, *B;
  102.  
  103.   A = (char *)ItemPtr;                /* Find the comparison data indicated
  104.                                        * by ItemPtr.  In our case, the data
  105.                                        * is a string, and ItemPtr already
  106.                                        * points to it.  We simply typecast
  107.                                        * ItemPtr to the correct pointer type.
  108.                                        * This is typically what you would
  109.                                        * need to do.
  110.                                        */
  111.   B = ((SampleRecPtr)NodePtr)->Name;  /* Find the data connected to the node
  112.                                        * that is in the tree.  Remember that
  113.                                        * this function gets a pointer to the
  114.                                        * ubi_trNode structure.  Convert the
  115.                                        * Node pointer to a pointer to our
  116.                                        * record type, then find the data item
  117.                                        * within that node.
  118.                                        */
  119.   return( strcmp( A, B ) );           /* Now compare and return the result. */
  120.   } /* CompareFunc */
  121.  
  122. static void PrintNode( ubi_trNodePtr NodePtr, void *Userdata )
  123.   /* ------------------------------------------------------------------------ **
  124.    * Print out the contents of a record stored in the tree.
  125.    *  Input:  NodePtr  - A pointer to the Node structure part of a record.
  126.    *          UserData - In this program, we're using this to pass in a
  127.    *                     a pointer to an integer.
  128.    * ------------------------------------------------------------------------ **
  129.    */
  130.   {
  131.   SampleRecPtr RecPtr;
  132.   int         *IntPtr;
  133.  
  134.   RecPtr = (SampleRecPtr)NodePtr; /* RecPtr now points to the entire record. */
  135.   IntPtr = (int *)Userdata;       /* IntPtr points to the integer.           */
  136.  
  137.   (*IntPtr)++;              /* Increment the integer indicated via Userdata. */
  138.   (void)printf( "%d: %s\n", *IntPtr, RecPtr->Name );
  139.   } /* PrintNode */
  140.  
  141. static void KillNode( ubi_trNodePtr NodePtr )
  142.   /* ------------------------------------------------------------------------ **
  143.    * Free the memory associated with a node (free the entire record).
  144.    *  Input:  NodePtr  - A pointer to a node in the tree.
  145.    * ------------------------------------------------------------------------ **
  146.    */
  147.   {
  148.   /* This could be very complicated if your data portion includes pointers to
  149.    * all sorts of other allocated memory.  In our case, it's quite simple.
  150.    */
  151.   free( NodePtr );
  152.   } /* KillNode */
  153.  
  154. int main( int argc, char *argv[] )
  155.   /* ------------------------------------------------------------------------ **
  156.    * Program main line.
  157.    * ------------------------------------------------------------------------ **
  158.    */
  159.   {
  160.   char          s[1024];
  161.   SampleRecPtr  RecPtr;
  162.   int           i;
  163.   char         *ModInfo[2];
  164.  
  165.   for( i = ubi_trModuleID( 2, ModInfo ); i > 0; )
  166.     (void)printf( "%s", ModInfo[--i] );
  167.  
  168.   (void)ubi_trInitTree( RootPtr,      /* Pointer to the tree header           */
  169.                         CompareFunc,  /* Pointer to the comparison function.  */
  170.                         0 );          /* Don't allow overwrites or duplicates.*/
  171.                                       /* See the Insert() notes in BinTree.h. */
  172.  
  173.   (void)printf( "Input string (blank line to exit)> " );
  174.   while( gets( s ) && strlen(s) )
  175.     {
  176.     /* Allocate a new node to be added to the tree. */
  177.     RecPtr = (SampleRecPtr)malloc( sizeof(SampleRec) );
  178.     if( !RecPtr )
  179.       {
  180.       perror( "main" );
  181.       exit( EXIT_FAILURE );
  182.       }
  183.  
  184.     /* Copy the new data into the record. */
  185.     s[NAMESIZE-1] = '\0';             /* Make sure the string is short enough.*/
  186.     (void)strcpy( RecPtr->Name, s );  /* Copy the string into our new record. */
  187.  
  188.     /* Add the record to the tree. */
  189.     if( !ubi_trInsert( RootPtr,       /* To which tree are we adding this?    */
  190.                        RecPtr,        /* The new node to be added.            */
  191.                        RecPtr->Name,  /* Points to the comparison field.      */
  192.                        NULL )         /* Overwrites are not allowed.          */
  193.       )
  194.       {
  195.       (void)fprintf( stderr, "Error: Duplicate key.  Record not added.\n" );
  196.       free( RecPtr );
  197.       }
  198.     (void)printf( "Input string (blank line to exit)> " );
  199.     }
  200.  
  201.   /* Now that the tree is full, dump it in sorted order. */
  202.   i = 0;
  203.   (void)ubi_trTraverse( RootPtr,    /* Tree root pointer. */
  204.                         PrintNode,  /* Pointer to function that prints out
  205.                                      * record contents.
  206.                                      */
  207.                         &i );       /* Userdata is typically not needed.
  208.                                      * This is an example of what you can
  209.                                      * do with it.
  210.                                      */
  211.   (void)printf( "A total of %d records found.\n", i );
  212.  
  213.   /* Now free all nodes in the tree. */
  214.   (void)ubi_trKillTree( RootPtr,    /* Tree root pointer. */
  215.                         KillNode ); /* Function that frees the node. */
  216.   return( EXIT_SUCCESS );
  217.   } /* main */
  218.  
  219. /* ========================================================================== */
  220.